package com.company.arithmetic;

/**
 * Created by v on 17-2-22.
 */
public class optimalBintree {
    public static void main(String[] args) {
        String[] words={"two","the","if","egg","and","am","a"};

        int[] amounts={8,2,25,5,20,18,22};

        System.out.println(dynamic(words,amounts));
    }

    public static int dynamic(String[] words,int[] amounts){
        //标记单词的数量
        int n=amounts.length;

        //先根据words对amounts进行排序
        for(int i=0;i<n;i++){
            for(int j=1;j<n;j++){
                if(words[j-1].compareTo(words[j])>0){
                    String tempWord=words[j-1];
                    int tempAmount=amounts[j-1];
                    amounts[j-1]=amounts[j];
                    words[j-1]=words[j];
                    amounts[j]=tempAmount;
                    words[j]=tempWord;
                }
            }
        }

        int[][] weight=new int[n+2][n+2];

        //计算第一次的值
        for(int i=1;i<=n;i++){
            weight[i][i]=amounts[i-1];
        }

        for(int i=2;i<=n;i++){
            for(int j=i;j<=n;j++){
                int k=j-i+1;
                int sum=0;
                for(int l=k;l<=j;l++){
                    sum+=amounts[l-1];
                }
                //最小的权值
                int min=Integer.MAX_VALUE;
                for(int l=k;l<=j;l++){
                    if(weight[k][l-1]+weight[l+1][j]<min){
                        min=weight[k][l-1]+weight[l+1][j];
                    }
                }
                weight[k][j]=min+sum;
            }
        }

        return weight[1][n];
    }
}
